AtCoder Beginner Contest 318

Full Moon

模拟。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), p = io.nextInt();
    io.println(n < m ? 0 : (n - m) / p + 1);
}

Overlapping sheets

比赛时没什么思路，想到扫描线，就用扫描线 + 区间合并来做了。结果一看题解，暴力标记每个点，没想到。

public static void solve() {
    int n = io.nextInt(), ans = 0;
    int[][] g = new int[100][100];
    for (int i = 0; i < n; i++) {
        int a = io.nextInt(), b = io.nextInt();
        int c = io.nextInt(), d = io.nextInt();
        for (int x = a; x < b; x++) {
            for (int y = c; y < d; y++) {
                if (g[x][y]++ == 0) ans++;
            }
        }
    }
    io.println(ans);
}

Blue Spring

看到大佬的解法后，感觉我模拟的方式好蠢啊。当时我是枚举是否要买 \(d\) 张票，有点麻烦，原来枚举买当日的票更简单。

public static void solve() {
    int n = io.nextInt(), d = io.nextInt(), p = io.nextInt();
    int[] f = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        f[i] = io.nextInt();
    }
    Arrays.sort(f);
    long ans = Long.MAX_VALUE, sum = 0L;
    for (int i = 0; i <= n; i++) {
        sum += f[i];
        ans = Math.min(ans, sum + (long) (n - i + d - 1) / d * p);
    }
    io.println(ans);
}

General Weighted Max Matching

动态规划有点不太会，赛时瞎搞 AC 的。记忆化搜索会很好写，然后 DP 的话，我是用三层循环解决的，下面的解法优化掉一层循环。

public static void solve() {
    int n = io.nextInt();
    int[][] d = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            d[i][j] = io.nextInt();
        }
    }
    long[] dp = new long[1 << n];
    for (int k = 2; k < 1 << n; k++) {
        int i = Integer.numberOfTrailingZeros(k & -k);
        dp[k] = dp[k ^ (1 << i)];
        for (int j = i + 1; j < n; j++) {
            if ((k >> j & 1) == 1) {
                dp[k] = Math.max(dp[k], dp[k ^ (1 << i) ^ (1 << j)] + d[i][j]);
            }
        }
    }
    io.println(dp[(1 << n) - 1]);
}

Sandwiches

比较显然的做法是把相同的数分为一组，然后组内枚举中间的数。对于每个中间的数，让答案加上 \(L\times R\)，其中 \(L\) 和 \(R\) 分别是左右两边相等的数的个数，枚举时可以一次性枚举间隔内所有数。

第二个解法是参考大佬的代码得到的，相当于枚举右端点吧。对于每个右端点，它的贡献可以根据下面代码中的公式得出，感觉比较巧妙。

public static void solve() {
    int n = io.nextInt();
    int[] cnt = new int[n];
    long[] sum = new long[n];
    long ans = 0L;
    for (int i = 0; i < n; i++) {
        int a = io.nextInt() - 1;
        ans += (long) i * cnt[a] - sum[a] - (long) (1 + cnt[a]) * cnt[a] / 2;
        cnt[a]++;
        sum[a] += i;
    }
    io.println(ans);
}

Octopus

有点抽象，不是很懂。大概是枚举了 \(N^{2}\) 个极限位置，然后分别对每个位置判断可行性。

public static void solve() {
    int N = io.nextInt();
    long[] X = new long[N];
    long[] L = new long[N];
    for (int i = 0; i < N; i++) {
        X[i] = io.nextLong();
    }
    for (int i = 0; i < N; i++) {
        L[i] = io.nextLong();
    }

    List<Long> pos = new ArrayList<>();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            pos.add(X[i] - L[j]);
            pos.add(X[i] + L[j] + 1);
        }
    }
    Collections.sort(pos);

    long ans = 0L;
    for (int i = 0; i < pos.size() - 1; i++) {
        long[] dis = new long[N];
        for (int j = 0; j < N; j++) {
            dis[j] = Math.abs(pos.get(i) - X[j]);
        }
        Arrays.sort(dis);
        boolean ok = true;
        for (int j = 0; j < N; j++) {
            if (dis[j] > L[j]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            ans += pos.get(i + 1) - pos.get(i);
        }
    }
    io.println(ans);
}